W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Marcin is peeling a potato. For simplicity, we assume that the potato is a convex polygon1, which edge is called a rind.
Marcin can perform straight cuts with his knife. With each cut, Marcin selects some straight line, along which a cut is being performed. After a cut is done, he throws away one of the parts of the potato. All points along the cut-line are also thrown away, so for instance when cutting along the line containing some edge belonging to the rind of the potato, that edge gets peeled.
A potato is said to be peeled only when it does not contain any point of the original rind. Marcin wants to perform as little work as possible when peeling the potato, which is why he would like to peel it with a limited number of cuts. Nevertheless, he wants to maximize the size of the peeled potato. What is the largest area of the pealed potato that can be obtained with at most cuts?
Write a program which:
In the first line of the standard input there are two integers () and (), separated by a single space and denoting the number of vertices of the polygon representing a potato under consideration and the maximal number of cuts that Marcin wants to perform to peel the potato. The following lines contain a description of the following vertices of the potato. They are specified in clockwise or anti-clockwise order. Each line contains two integers and , , representing coordinates of the following potato's vertex.
In the first and only line of the standard output your program should write one real number, written with exactly one digit after the dot and representing the largest possible area of the peeled potato that can be obtained with at most cuts. You should not round this number, the second and following digits after the dot do not impact the outcome.
For the input data:
5 3 0 0 3 1 6 4 3 7 0 8
the correct result is:
24.0
Sample potato can be optimally peeled with cuts in the way
demonstrated above.
Task author: Marcin Pilipczuk.